package org.labuladong.前缀和技巧;

import java.util.HashMap;
import java.util.Map;

/**
 * @Auther: qingle
 * @Date: 2024/10/25-21:02
 * @Description:
 *
 * 给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。
 *
 * 前缀和解法
 *
 * 前缀和不难，却很有⽤，主要⽤于处理数组区间的问题。
 * ⽐如说，让你统计班上同学考试成绩在不同分数段的百分⽐，也可以利⽤前
 * 缀和技巧：
 *
 * 让你统计班上同学考试成绩在不同分数段的百分⽐，也可以利⽤前
 * 缀和技巧：
 * int[] scores; // 存储着所有同学的分数
 * // 试卷满分 150 分
 * int[] count = new int[150 + 1]
 * // 记录每个分数有⼏个同学
 * for (int score : scores)
 * count[score]++
 * // 构造前缀和
 * for (int i = 1; i < count.length; i++)
 * count[i] = count[i] + count[i-1];
 *
 * @version: 1.0
 */
public class LCR010_和为K的子数组_前缀和 {
		public int subarraySum(int[] nums, int k) {
			int n = nums.length;
			int count = 0; // 用于记录和为k的子数组的数量
			long sum = 0; // 滑动窗口的和，使用long防止溢出
			Map<Long, Integer> preSum = new HashMap<>(); // 用于存储前缀和出现的次数，初始0次
			preSum.put(0L, 1); // 初始化时，前缀和为0的情况有1次

			// 遍历数组，使用滑动窗口来计算和为 k 的子数组的数量
			for (int i = 0; i < n; i++) {
				sum += nums[i]; // 将当前元素加入到窗口中

				// 检查sum - k之前是否出现过，如果出现过，说明存在和为k的子数组
				if (preSum.containsKey(sum - k)) {
					count += preSum.get(sum - k);
				}

				// 更新map中对应前缀和的计数
				preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
			}

			return count; // 返回和为k的子数组的数量
		}

	public static void main(String[] args) {

		/**
		 * 代码解释：
		 * 初始化变量：定义变量 count 来记录和为 k 的子数组的数量，sum 来记录当前窗口的和，以及一个 HashMap 来存储不同前缀和出现的次数。
		 *
		 * 遍历数组：使用一个 for 循环遍历数组 nums。
		 *
		 * 更新窗口和：在每次循环中，将当前元素加入到窗口的和中。
		 *
		 * 检查和为 k 的子数组：在每次循环中，检查当前窗口和减去 k 是否在 HashMap 中已经出现过。如果出现过，说明从上一个前缀和为 sum - k 的位置到当前位置的子数组和为 k，因此将这个前缀和的出现次数加到 count 上。
		 *
		 * 更新 HashMap：无论是否找到和为 k 的子数组，都更新 HashMap 中对应前缀和的计数。
		 *
		 * 返回结果：遍历完成后，返回 count 作为结果。
		 *
		 * 这个方法的时间复杂度是 O(n)，其中 n 是数组 nums 的长度，因为我们只需要遍历一次数组。空间复杂度是 O(n)，这是因为在最坏的情况下，我们可能需要存储所有前缀和及其出现的次数。
		 */

		int[] nums = {1, 2, 3, 4, 5};
		int k = 3;
		LCR010_和为K的子数组_前缀和 solution = new LCR010_和为K的子数组_前缀和();
		int result = solution.subarraySum(nums, k);
		System.out.println(result);
	}
}
